// https://www.lintcode.com/problem/maximum-vacation-days/description

// 可以用DFS做，但会超时，所以改成DP解法。

// 起始状态为在最后一个week里面在每个city所能呆的最长时间
// 然后从后往前更新DP数组，需要考虑flights的限制
// 最后在第一天的DP数组里面，找出从city 0能到达的里面天数最大的即可

// 题解：
// dp[i]表示最后到达i城市的最长休假时间。先枚举周数，然后枚举终点，然后是起点，判断是否前往(temp[j] = Math.max(temp[j], dp[k] + days[j][i]);)，即是否进行转移。每周更新dp数组，最后从dp数组选择最大值即可。

class Solution {
public:
    /**
     * @param flights: the airline status from the city i to the city j
     * @param days: days[i][j] represents the maximum days you could take vacation in the city i in the week j
     * @return: the maximum vacation days you could take during K weeks
     */
    int maxVacationDays(vector<vector<int>> &flights, vector<vector<int>> &days) {
        // Write your code here
        int N = flights.size();
        int K = days[0].size();
        vector<int> dp(N, INT_MIN);
        dp[0] = 0;
        for (int i = 0; i < K; i++) {     //逐渐扩大枚举周    
            vector<int> temp(N, INT_MIN);
            for (int j = 0; j < N; j++) {       //枚举终点
                for(int k = 0; k < N; k++) {     //枚举起点
                    if (j == k || flights[k][j] == 1) {   //如果城市k到城市j存在航班
                        temp[j] = max(temp[j], dp[k] + days[j][i]);   //则再对当前答案进行选择，即是否从k前往j
                    }
                }
            }
            dp = temp;
        }
        
        int ans = 0;
        for(int i = 0; i < N; i++){    //最后对dp数组筛选最大值即可
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};